//***********************************快速排序***************************************
// 定一个枢轴（一般取一个数列的第一项），将比枢轴值大的放到枢轴左侧，大的放右侧
// 形成两个子表，再对这两个子表使用同样的方法（递归）
// 每一次子表的形成都只是用一个空间位，两头向中间交替式逼近
// 平均时间复杂度：O(nlogn)最优
// 空间复杂度：O(logn)
// 不稳定排序，且不适用于对基本有序的表进行排序，会退化为冒泡排序

// 快速排序入口函数
function quickSort(arr) {
  qsByRecursion(arr, 0, arr.length-1)
}
  // 递归辅助函数
  function qsByRecursion(arr, lowIndex, highIndex) {
    if(lowIndex <= highIndex) {
      //寻找枢轴值的下标位置
      let pivotIndex = getPivotIndex(arr, lowIndex, highIndex)
      //递归处理左子表
      qsByRecursion(arr, lowIndex, pivotIndex-1)
      //递归处理右子表
      qsByRecursion(arr, pivotIndex+1, highIndex)
    }
  }
  //找中心点辅助函数
  function getPivotIndex(arr, low, high) {
    //暂存枢轴值
    let pivotTemp = arr[low]
    //左右指针交替逼近
    while(low < high) {
      //从右向左搜，找比枢轴小的第一个high下标，将其值赋给low所在位置
      while(arr[high] >= pivotTemp && low < high) {
        high--
      }
      arr[low] = arr[high]
      //从左向右搜，找比枢轴大的第一个low下标，将其值赋给high所在位置
      while(arr[low] < pivotTemp && low < high) {
        low++
      }
      arr[high] = arr[low]
    }
    //找到的 low = high 就应该是枢轴值最终应该所在的下标位置
    //此时整个无序表被分割为了左右两个子表
    arr[low] = pivotTemp
    return low
  }

//测试用例
let arr = [49,38,65,97,76,13,27,30]
quickSort(arr)
console.log(arr);